package bTree.LeetCode;

public class 腐烂的橘子 {
    int sum = 0;
    int[][] dir = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    int pot = 0;
    int incr;
    int minute = 0;

    public int orangesRotting(int[][] grid) {
        int row = grid.length;
        int line = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < line; j++) {
                int item = grid[i][j];
                if (1 == item) {
                    sum++;
                }
                if (2 == item) {
                    sum++;
                    pot++;
                }
            }
        }
        if (sum==pot){
            return 0;
        }
        while (true) {
            incr = 0;
            boolean[][] visited = new boolean[row][line];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < line; j++) {
                    int item = grid[i][j];
                    if (2 == item && !visited[i][j]) {
                        dfs(grid, visited, i, j);
                    }
                }
            }
            pot += incr;
            minute++;
            if (pot == sum) {
                return minute;
            }
            if (incr == 0) {
                return -1;
            }

        }
    }

    private void dfs(int[][] grid, boolean[][] visited, int row, int line) {
        visited[row][line] = true;
        for (int i = 0; i < 4; i++) {
            int newLine = line + dir[i][0];
            int newRow = row + dir[i][1];
            if (newLine < 0 || newLine >= grid[0].length || newRow < 0 || newRow >= grid.length || grid[newRow][newLine] == 0 || grid[newRow][newLine] == 2||visited[newRow][newLine]) {
                continue;
            }
            grid[newRow][newLine]=2;
            visited[newRow][newLine] = true;
            incr++;
        }
    }
}